An interconnection network consists of a set of nodes connected by channels. Such networks are used to transport data packets between nodes. They are used, for example, in multicomputers, multiprocessors, and network switches and routers. In multicomputers, they carry messages between processing nodes. In multiprocessors, they carry memory requests from processing nodes to memory nodes and responses in the reverse direction. In network switches and routers, they carry packets from input line cards to output line cards. For example, pending U.S. patent application Ser. No. 08/918,556, filed by William J. Dally, Philip P. Carvey, Larry R. Dennison and P. Alan King for Internet Switch Router, describes the use of a three-dimensional torus interconnection network to provide the switching fabric for an internet router.
The arrangement of the nodes and channels in a network defines its topology. FIG. 1, for example, illustrates a two-dimensional, radix-8 torus topology, also called an 8-ary 2-cube. In this topology each node is designated by a two-digit radix-8 address. Channels in both directions connect each pair of nodes whose addresses differ by one in exactly one digit modulo 8. That is, node (a,b) is connected to nodes (axe2x88x921,b),(a+1,b),(a,bxe2x88x921), and (a,b+1) where the addition and subtraction are performed modulo-8. Each node in this topology has degree 4 since it is connected to four other nodes. A related topology, an 8-ary 2-mesh, is shown in FIG. 2. This network is identical to the 8-ary 2-cube except that the xe2x80x98end-aroundxe2x80x99 connections from node 7 to node 0 in each dimension are omitted. While the mesh network is simpler to wire, it has significantly lower performance than the torus network as will be described below.
Meshes and tori may be constructed with different radices and numbers of dimensions, and other network topologies are possible such as crossbars, trees, and butterfly networks. Several popular topologies are described, for example, by William J. Dally, xe2x80x9cNetwork and Processor Architectures for Message-Driven Computers,xe2x80x9d in VLSI and Parallel Computation, Edited by Suaya and Birtwistle, Morgan Kaufmann, 1990.
The topology chosen for an interconnection network is constrained by the technology used to implement the network. Pin-count constraints on chips, circuit boards, and backplanes, for example, limit the maximum degree of each network node. Wire-length constraints limit the maximum distance a single channel can traverse when the network is mapped into a physical packaging structure.
Low-dimensional (2-3 dimensions) torus and mesh networks have become popular in recent years in part because they offer good performance while having a small node degree and uniformly short wires when mapped to two or three dimensional electronic packaging systems. While at first it may appear that the end-around channels in a torus network result in long wires, these long wires can be avoided by folding the torus as illustrated in FIG. 3. The figure shows how an 8xc3x974 torus that is folded in the x-dimension is mapped onto a set of backplanes 20. Each node is packaged on a circuit card and eight of these circuit cards are inserted in each backplane 20. The circuit cards in each backplane span two x coordinates and the entire y dimension. The y-dimension channels are realized entirely in the backplane while the x-dimension channels are realized by connections between backplanes. Folding the torus allows this topology to be realized with each x-channel connecting no further than the adjacent backplane.
To expand the network of FIG. 3, it is necessary to first break the loopback connection 22 or 24 at the end of the x-dimension and then make a connection to a new backplane. An efficient method for reconfiguring the network in this manner is disclosed in pending U.S. patent application Ser. No. 09/083,722, filed by Philip P. Carvey, William J. Daily and Larry R. Dennison for Apparatus and Methods for Connecting Modules Using Remote Switching.
Two important measures of the quality of a topology are average path length and maximum channel load. The average path length, Davg, of a network is the average number of channels that must be traversed to send a packet between two randomly selected nodes in a network. In the radix-8, two-dimensional torus network of FIG. 1, the average packet traverses two channels in each dimension, giving Pavg=4. In general, the average path length in a k-ary n-cube is kn/4 (for k even) and n(k/4-1/4k) (for k odd) while the average path length in a k-ary n-mesh is n(k/3-1/3k). Average path length is a good predictor of network latency. The lower the average path length of a topology, the lower is the latency of a network using that topology, assuming the latency of an individual channel remains constant.
The maximum channel load of a network, Cmax, is the largest number of packets that traverse a single channel when all nodes send packets to all other nodes divided by the number of nodes squared. In the 8-ary 2-cube network of FIG. 1, for example, the channel load is uniform with Cmax=Ci=1 for every channel i. In general, the maximum channel load in a k-ary n-cube is k/8 while the maximum channel load in a k-ary n-mesh is k/4. Maximum channel load is a good predictor of the throughput of a network. The lower the maximum channel load of a topology, the higher is the throughput of a network using that topology, assuming the bandwidth of an individual channel remains constant.
While the folded torus network offers a method of packaging a regular k-ary n-cube network so that all of the channels remain short, it is inherently inefficient because nodes that are packaged very close to one another can communicate only via circuitous routes. For example, in FIG. 3, nodes (2,0) and (7,0) are on the same backplane. A message from (2,0) to (7,0), however, must leave this backplane and traverse five backplane-backplane connections before arriving back at the backplane. The problem becomes even more acute as the x-dimension grows in radix. A more efficient topology would minimize this off-backplane communication by allowing direct communication between nodes on the same backplane. A more efficient topology would also provide good performance without needing an end-around connection that must be removed for expansion.
One mechanism for increasing system performance in terms of average path length and maximum channel load and for making a network less susceptible to loss of end around connections is to add one or more dimensions to the network. However, adding a dimension increases the node degree by two, thus increasing the complexity of each node.
In accordance with one aspect of the invention, benefits of an added dimension without the increased node degree can be obtained by connecting one subset of channels within the network in one dimension and connecting another subset of the network channels in a different dimension. By distributing the nodes connected by the two channel subsets throughout the network, messages transferred through the network always have ready access to each dimension, but since each node need only be connected to one dimension or the other, there is no increase in degree. The concept of interleaving differing connections along one or more dimensions can be extended to other configurations for improved performance. Further, connections can be modified to assure that all nodes on a backplane, for example, are connected in a single cycle. The increased path lengths between some nodes resulting from the addition of such local connections can generally be masked by alternating the configurations from backplane to backplane.
In accordance with the invention, a plurality of channels connect a plurality of nodes in each connection network. A first subset of the channels connects the nodes is in a first dimension. A second subset of the channels connects the nodes in at least a second dimension, and connection of the second subset of channels differs at different coordinates along the first dimension.
In a preferred embodiment, the second subset of the channels connects the nodes in cycles or linear arrays in a second dimension and the ordering of the nodes in cycles or linear arrays is different at different coordinates along the first dimension. A connection of the second subset of channels at a first set of coordinates in the first dimension connects nodes whose coordinates in the second dimension differ by a first number. The connection of the second subset of channels in a second set of coordinates in the first dimension connects nodes whose coordinates in the second dimension differ by a second number. Thus, for example, in even numbered positions along the x-dimension, adjacent nodes in the backplane may be connected. However, in odd numbered positions, every other node may be connected.
Preferably, cycles or linear arrays of the second subset of the channels connect multiple nodes of each of plural cycles or linear arrays in the first dimension. For example, where the channels of the first dimension are folded, the second subset of the channels may connect nodes on opposite sides of the folds, thus reducing loading in the first dimension.
A first set of coordinates in the first dimension of the second subset of channels may connect the nodes into a cycle or linear array along a second dimension while, at a second set of coordinates in the first dimension, the second subset of channels connect the nodes into a cycle or linear array along a third dimension.
A preferred embodiment of the invention is a three-dimensional array. The second subset of the channels includes channel connecting nodes in a second dimension and channels connecting nodes in a third dimension. The connections in the third dimension differ at different coordinates of the first and second dimensions.
Nodes connected in at least the second dimension at a coordinate along the first dimension may be packaged in a single packaging module, such as on a backplane or other circuit board.